package 堆;

import java.util.PriorityQueue;

/**
 * @author TTDB
 * @create 2025/9/23
 */

    /**
 * MedianFinder类用于动态维护一组数据的中位数
 * 使用两个堆来实现高效查找中位数的功能
 */
public class MedianFinder {

    /**
     * 最小堆，存储较大的一半数据，堆顶为最小元素
     */
    private PriorityQueue<Integer> minHeap;

    /**
     * 最大堆，存储较小的一半数据，堆顶为最大元素
     */
    private PriorityQueue<Integer> maxHeap;

    /**
     * 构造函数，初始化两个堆
     * minHeap使用默认的最小堆比较器
     * maxHeap使用自定义的最大堆比较器
     */
    public MedianFinder() {
         minHeap = new PriorityQueue<>();
         maxHeap = new PriorityQueue<>((a, b) -> b - a);
     }

     /**
      * 添加一个新的数字到数据结构中
      * 保持两个堆的平衡，确保大小差异不超过1
      */
     public void addNum(int num) {
         // 如果minHeap为空或者num小于等于minHeap的堆顶元素，则添加到minHeap
         if (minHeap.isEmpty() || num <= minHeap.peek()) {
             minHeap.offer(num);
             // 如果minHeap比maxHeap多出超过1个元素，则移动一个元素到maxHeap
             if (minHeap.size() > maxHeap.size() + 1) {
                 maxHeap.offer(minHeap.poll());
             }
         } else {
             // 否则添加到maxHeap
             maxHeap.offer(num);
             // 如果maxHeap比minHeap多出超过1个元素，则移动一个元素到minHeap
             if (maxHeap.size() > minHeap.size() + 1) {
                 minHeap.offer(maxHeap.poll());
             }
         }
     }

     /**
      * 查找当前所有数据的中位数
      * 如果两个堆大小相等，返回两个堆顶的平均值
      * 如果不相等，返回较大堆的堆顶元素
      */
     public double findMedian() {
         // 如果两个堆大小相等，返回两个堆顶元素的平均值
         if (minHeap.size() == maxHeap.size()) {
             return (minHeap.peek() + maxHeap.peek()) / 2.0;
         } else {
             // 否则返回较大堆的堆顶元素
             return minHeap.size() > maxHeap.size() ? minHeap.peek() : maxHeap.peek();
         }
     }
}
